package com.kehao.leetcode.algorithm;

import org.junit.Test;

public class Solution208 {
    private static class Trie {
        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            isEnd = false;
            children = new Trie[26];
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length()-1; i++) {
                char c = word.charAt(i);
                if(node.children[c-'a']==null){
                    node.children[c-'a'] = new Trie();
                }
                node = node.children[c-'a'];
            }
            char c = word.charAt(word.length()-1);
            if(node.children[c-'a']==null){
                node.children[c-'a'] = new Trie();
            }
            node.children[c-'a'].isEnd = true;
        }

        public boolean search(String word) {
            Trie node = this;
            for (int i = 0; i < word.length()-1; i++) {
                if(node.children[word.charAt(i)-'a']==null){
                    return false;
                }
                node = node.children[word.charAt(i)-'a'];
            }
            int index = word.charAt(word.length()-1)-'a';
            if(node.children[index]==null||node.children[index].isEnd==false){
                return false;
            }
            return true;
        }

        public boolean startsWith(String prefix) {
            Trie node = this;
            for (int i = 0; i < prefix.length()-1; i++) {
                if(node.children[prefix.charAt(i)-'a']==null){
                    return false;
                }
                node = node.children[prefix.charAt(i)-'a'];
            }
            int index = prefix.charAt(prefix.length()-1)-'a';
            if(node.children[index]==null){
                return false;
            }
            return true;
        }
    }


    @Test
    public void test01(){
        Trie trie = new Trie();
        trie.insert("app");
        trie.insert("apple");
        System.out.println(trie.search("app"));
    }

}
